Section: Research Program

Computer algebra

We aim to further reinforce our expertise in the computer algebra aspects of functional systems and algebraic curves by attacking remaining technical obstacles and by considering new classes of functional systems, notably those coming from interesting applications in engineering sciences and particularly in control theory.

Efficient algorithms for the study of singularities of algebraic curve and its applications

On an algorithmic viewpoint, there are mainly four different approaches for the study of the singularities of plane algebraic curves. Let us shortly list them:

• The well-known Newton-Puiseux algorithm, initiated by Cramer and Puiseux, which follows an idea due to Newton. This approach has successively been improved in [61], [88], [9], [10].

• The Extended Hensel Construction, developed in [74] and recently improved in [82].

• The work [68] concentrates on the factorisation of polynomials defined over valued fields (the local study of a plane algebraic curve enters in this approach).

• The work [33] introduces the concept of anapproximate root.

The first two methods are based on Puiseux series computations. They use techniques which are equivalent to the standard blowing-up of a singularity of an algebraic curve, which has the drawback to be bottlenecks in terms of complexity and practical efficiency. Nevertheless, the recent work [88] provides the best complexity currently known. The last two methods study singularities without computing Puiseux series. They both use the concept of an extended evaluation.

A recent very efficient algorithm for the factorisation of a univariate polynomial based on its Newton polygon has recently been obtained in [52]. The key ingredient of this algorithm is to work on the given polynomial and not after changes of variables as usually done in the literature.

To improve the complexity results of [68], [38], we want to combine the above different approaches using approximate roots and a generalization of the results of [52] to the context of [68].

The method proposed above is important in practice since it is based on well-known and efficiently implemented algorithms (mainly Newton iteration and gcd computations). Nevertheless, these algorithms involve technical difficulties on the computer science side: the main one is the need to improve the accuracy of computations due to truncations. These issues, including also run-time compilation, are well-studied in the BPAS library (http://www.bpaslib.org/index.html) based on specific data structures to deal with power series computation (a power series is represented by terms that have been computed and a program that enables to compute more terms when required).

Another part of the code development concerns issues on certified numerical computations for univariate polynomials (with algebraic coefficients) that will be used for the development of certified symbolic-numeric algorithms making effective the strategy proposed in [87].

Differential algebra

A major bottleneck of computational differential algebra methods is the computation of greatest common divisors of multivariate commutative polynomials. Any algorithmic progress in this direction would highly improve the efficiency of differential algebra software such as, for instance, the C library BLAD [44]. Moreover, numerous computer algebra problems and related implementations could also highly profit from any success in this direction.

A major application of the effective differential algebra approach developed by GAIA's members [45], [46] is the possibility to reduce a nonlinear (implicit) differential system, particularly differential algebraic equations, to so-called regular chains of differentiation index 0, i.e. to systems which do not need differentiation of their equations to be rewritten as pure differential systems [69]. Based on our expertise on differential techniques, we want to study the consistent initialization problem and develop numerical integrators for nonlinear differential algebraic systems, and used them in the study of coupled algebraic and differential systems, interconnected systems, or networks [69].

A Maple package and a C /C ++ open source library for integro-differential algebra

A package dedicated to nonlinear integro-differential equations will be developed in a Maple prototype and then in a standalone C /C ++ open source library (as it was already done for the diffalg and DifferentialAlgebra packages). General purpose solvers such as Maple dsolve or pdesolve may call differential elimination methods for computing essential singular solutions of differential equations, for computing systems of polynomial differential equations admitting a given function as a solution, etc. On the long run, one may foresee enhanced general purpose solvers able to handle integro-differential equations processed through integro-differential elimination methods. It will rely on a sub-package dedicated to the problem of effectively handling integro-differential expressions.

These packages will rely on existing software such as BLAD , DifferentialAlgebra , and MABSys . It is worth pointing out that proof-of-concept methods are already available. See [29] and [2]. The collaboration with modelers will also enhance the software user-interface for a better usability.

The study of numerical integration of integro-differential equations (a necessary component of software dedicated to the parameter estimation problem) will also be further studied following the direction initiated in [29], leading to the Maple/C library BLINEIDE . This software has currently no widely available challenger.

The Maple prototype software dedicated to nonlinear integro-differential equations will also be implemented in a standalone C /C ++ open source library, leading to software easier to integrate in modeling platforms such as OpenModelica . The GAIA team has quite some expertise in releasing software satisfying industrial standards: its C open source BLAD libraries, dedicated to differential elimination, are currently integrated in Maple and called through the Maple package DifferentialAlgebra . The Modelica programming language, which emphasizes programming with equations and permits to call external code, can integrate software dedicated to integro-differential equations developed in the GAIA team.